// https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 单调栈解决每日温度问题（下一个更高温度）
// 2. 维护温度递减的单调栈（存储下标）
// 3. 当前温度高于栈顶时，计算等待天数并出栈
// 4. 最终栈中剩余元素表示没有更高温度（默认为0）
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <stack>

class Solution 
{
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) 
    {
        int m = temperatures.size();

        vector<int> ret(m, 0);
        stack<int> st;

        for (int i = 0 ; i < m ; i++)
        {
            while (!st.empty() && temperatures[st.top()] < temperatures[i])
            {
                int index = st.top();
                st.pop();
                ret[index] = i - index;
            }
            st.push(i);
        }

        return ret;
    }
};

int main()
{
    vector<int> temperatures1 = {73,74,75,71,69,72,76,73}, temperatures2 = {30,40,50,60};
    Solution sol;

    auto v1 = sol.dailyTemperatures(temperatures1);
    auto v2 = sol.dailyTemperatures(temperatures2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;

    return 0;
}